package com.leetcodehot.problems;

import java.util.ArrayDeque;
import java.util.Deque;

public class problems1438 {
    /**
     * 发现可以使用双端队列，应该是两个一个维护当前范围的最大 一个维护最小
     * 双指针移动，先尽量移动到最右，如果不行则移动左
     */

    public int longestSubarray(int[] nums, int limit) {
        Deque<Integer> up = new ArrayDeque<>();
        Deque<Integer> down = new ArrayDeque<>();
        int n = nums.length;
        int maxLen = 0;
        int left = 0;
        int right = 0;
        for (right = 0; right < n; right++) {
            //右指针向右移动，左指针先不动
            int x = nums[right];
            while (!up.isEmpty() && nums[up.getLast()] >= x) {
                up.removeLast();
            }
            up.addLast(right);
            while (!down.isEmpty() && nums[down.getLast()] <= x) {
                down.removeLast();
            }
            down.addLast(right);
            //维持队列,left为双端队列的起点，up最左为最小的，down最左是最大的
            while (!up.isEmpty() && !down.isEmpty() && Math.abs(nums[up.getFirst()] - nums[down.getFirst()]) > limit && left < right) {
                //违反了
                //右移动left
                if (!up.isEmpty() && up.getFirst() == left) {
                    up.removeFirst();
                }
                if (!down.isEmpty() && down.getFirst() == left) {
                    down.removeFirst();
                }
                left++;
            }
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}